package edu.thu.thss.rsa.yxy;

import java.math.BigInteger;
import java.util.ArrayList;
import java.util.HashMap;

/**
 * 最短加法链实现
 * 
 * @author Andy Gao
 *
 */
public class ShortAdditionChains {
	private final BigInteger TWO = new BigInteger("2");
	private final BigInteger THREE = new BigInteger("3");
	
	public static final Integer MAX_NUMBER = 1000;
	
	private HashMap<BigInteger, BigInteger> parent = new HashMap<BigInteger, BigInteger>();
	private HashMap<BigInteger, BigInteger> factor = new HashMap<BigInteger, BigInteger>();
	
	private ArrayList<BigInteger> chain = new ArrayList<BigInteger>();
	
	private int bestChainLength;
	private int lowerBound;
	private int upperBound;
	private int turn;
	private boolean isFound;
	private BigInteger powNum;
	
	
	public ShortAdditionChains(BigInteger powNum) {
		this.powNum = powNum;
	}

	public BigInteger[] getAdditonChains(){
		lowerBound = minimumChainLength(powNum);
		upperBound = maximumChainLength(powNum);
		turn = getTurn(powNum);
		
		if(lowerBound < upperBound){
			isFound = false;
			while(!isFound){
//				System.out.println("Lower Bound = " + lowerBound);
				factor.clear();
				parent.clear();

				factor.put(BigInteger.ZERO,BigInteger.ONE);
				
				backtraceFactorTree(0);
				lowerBound++;
				if(lowerBound == upperBound){
					isFound = true;
				}
			}
		}
		
		BigInteger[] addChains = new BigInteger[chain.size()];
		chain.toArray(addChains);
		
		return addChains;
	}

	// Lower bound: log2n + log2v(n)  - 2.13 < l(n) 
	private int minimumChainLength(BigInteger number) {
//		double minimumLength;
//
//		double logn = 0;
//		while(number.compareTo(BigInteger.ONE) > 0){
//			number = number.shiftRight(1);
//			logn++;
//		}
//		
//		byte[] cArray = number.toByteArray();
//		int numberOfOnes = 0;
//		for (int i = 0; i < cArray.length; i++) {
//			if (cArray[i] == 1) {
//				numberOfOnes++;
//			}
//		}
//
//		minimumLength = (logn + (Math.log(numberOfOnes) / Math.log(2)) - 2.13);
//		return (int)minimumLength;
		BigInteger temp = number;
		if(BigInteger.ZERO.compareTo(number.and(BigInteger.ONE)) == 0){
			temp = temp.add(BigInteger.ONE);
		}
		
		int minAddLength = 0;
		while(number.compareTo(BigInteger.ONE) > 0){
			number = number.shiftRight(1);
			minAddLength++;
		}
		
		return minAddLength;
		
	}
	
	//Upper bound: l(n)< |_log n _| + v(n) -1
	private int maximumChainLength(BigInteger number) {
		int maximumLength;
		maximumLength = buildFactorTree(number);
		return maximumLength;
	}
	
	private static int getTurn(BigInteger powNum) {
		int i = 0;
		while ((powNum.and(BigInteger.ONE)).compareTo(BigInteger.ZERO) == 0) {
			powNum = powNum.shiftRight(1);
			i++;
		}
		return i - 1;
	}

	private int buildFactorTree(BigInteger number) {
		isFound = false;
		upperBound = 0;

		while(!isFound){
			factor.clear();
			parent.clear();

			factor.put(BigInteger.ZERO,BigInteger.ONE);
			calcFactorTree(0);
			upperBound++;
		}
		return bestChainLength;
	}

	private void calcFactorTree(int step) {
		if(!isFound){
			if(ArrayItem(factor, step).compareTo(powNum) == 0){
				this.bestChainLength = step + 1;
				for(int i = 0; i <= step; i++){
					chain.add(i, ArrayItem(factor, i));
				}
				isFound = true;
				return;
			} else if(step <= upperBound){
				for(int i = 0; i <= step; i++){
				 	BigInteger temp = ArrayItem(factor,step).add(ArrayItem(factor, i));
					if(temp.compareTo(powNum) <= 0){
						factor.put(new BigInteger(String.valueOf(step + 1)), temp);
						int tempValue = temp.intValue();
						if(ArrayItem(parent, tempValue).compareTo(BigInteger.ZERO) == 0){
							parent.put(new BigInteger(String.valueOf(tempValue)), ArrayItem(factor, step));
						}
						if(ArrayItem(parent, tempValue).compareTo(ArrayItem(factor, step)) == 0){
							calcFactorTree(step + 1);
						}
					}
				}
			}
		} 
	}
	
	private void backtraceFactorTree(int step) {
		if (!isFound) {
			if (ArrayItem(factor, step).compareTo(powNum) == 0) {
				bestChainLength = step + 1;
				for (int i = 0; i <= step; i++) {
					chain.add(i, ArrayItem(factor, i));
				}
				isFound = true;
				return;
			} else if (step < lowerBound) {
				for (int i = step; i >= 0; i--) {
					if (ArrayItem(factor, i).multiply(TWO).compareTo(ArrayItem(factor, step)) > 0) {
						for (int j = i; j >= 0; j--) {
							BigInteger temp = ArrayItem(factor, i).add(ArrayItem(factor, j));
                            String stepOne = String.valueOf(step + 1); 
							factor.put(new BigInteger(stepOne), temp);
							if (temp.compareTo(ArrayItem(factor, step)) > 0  && temp.compareTo(powNum)<= 0) {
								if (!prunedFactorTree(step + 1)) {
									backtraceFactorTree(step + 1);
								}
							}
						}
					}
				}
			}// End Else If
		}
	}

	private boolean prunedFactorTree(int step) {
		if(step < lowerBound - turn - 1){
			BigInteger temp = ArrayItem(factor, step).multiply(THREE);
			int i = 0;
			while(temp.compareTo(powNum) < 0){
				temp = temp.shiftLeft(1);
				i++;
			}
			return (i + step + 2 > lowerBound);
		}else{
			BigInteger temp = ArrayItem(factor, step);
			int i = 0;
			while(temp.compareTo(powNum) < 0){
				temp = temp.shiftLeft(1);
				i++;
			}
			return (i + step > lowerBound);
		}
	}
	
	public BigInteger ArrayItem(HashMap<BigInteger, BigInteger> map, int key){
		BigInteger temp = map.get(new BigInteger(String.valueOf(key)));
		if(temp != null){
			return temp;
		}else{
			return BigInteger.ZERO;
		}
	}

	public int getBestChainLength() {
		return bestChainLength;
	}

	public static void main(String[] args){
//		System.out.println(MAX_NUMBER);
		BigInteger temp = new BigInteger("6");
		ShortAdditionChains ac = new ShortAdditionChains(temp);
		BigInteger[] chains = ac.getAdditonChains();
		for(int i = 0; i < ac.getBestChainLength(); i++){
			System.out.println(chains[i] + "	");
		}
	}
}
